package com.qfjy.student.zhangqingqqing.sort;

/**
 * @Author zhangqingqing
 * @Date 2021/6/23 21:00
 */

public class QuickSort {
    private static int[] a = {6,1,2,7,9,3,4,5,10,8};

    public static void main(String[] args){
        System.out.println("原数组值：");
        for (int i : a) {
            System.out.print(i+" ");
        }
        System.out.println();
        quickSort(0, a.length-1);
    }

    public static void quickSort(int left,int right){
        int i,j,temp;
        if(left>right){
            return;
        }
        temp=a[left]; //temp中存的就是基准数
        i=left;
        j=right;
        while(i!=j){
            //顺序很重要，要先从右边开始找 ，直到找到一个小于基准的值
            while(a[j]>=temp && i<j){
                j--;
            }
            //再找右边的 ，直到找到一个大于基准的值
            while(a[i]<=temp && i<j){
                i++;
            }
            //交换两个数在数组中的位置
            if(i<j) {
                int t=a[i];
                a[i]=a[j];
                a[j]=t;
                System.out.println("交换值后：");
                for (int k : a) {
                    System.out.print(k+" ");
                }
                System.out.println();
            }
        }
        //最终将基准数归位
        a[left]=a[i];
        a[i]=temp;
        System.out.println("基准值归位后：");
        for (int k : a) {
            System.out.print(k+" ");
        }
        System.out.println();
        if(left<i-1){
            quickSort(left,i-1);//继续处理左边的，这里是一个递归的过程
        }
        if(right>j+1){
            quickSort(i+1,right);//继续处理右边的 ，这里是一个递归的过程
        }
    }
//原数组值：
//6 1 2 7 9 3 4 5 10 8
//交换值后：
//6 1 2 5 9 3 4 7 10 8
//交换值后：
//6 1 2 5 4 3 9 7 10 8
//基准值归位后：
//3 1 2 5 4 6 9 7 10 8
//基准值归位后：
//2 1 3 5 4 6 9 7 10 8
//基准值归位后：
//1 2 3 5 4 6 9 7 10 8
//基准值归位后：
//1 2 3 4 5 6 9 7 10 8
//交换值后：
//1 2 3 4 5 6 9 7 8 10
//基准值归位后：
//1 2 3 4 5 6 8 7 9 10
//基准值归位后：
//1 2 3 4 5 6 7 8 9 10
}
